
// 首行是表示有几行输入
var readline = require('readline');

let rows = [];
let k = -1;
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
})

rl.on('line', line => {
  if (k == -1) {
    k = parseInt(line.trim());
  } else {
    rows.push(line);
    if (rows.length === k) {
      // 输入行数等于首行输入的数字的时候开始计算
      const arr = toArray(rows);
      console.log(arr);
      const root = arrToTree(arr);
      console.log(levelOrder(root));
      rl.close()
    }
  }
})

// 转变成数组
function toArray(rows) {
  const arr = [];
  rows.forEach(el => {
    // 每行输入的字符串 转变成数字数组
    let numArr = el.split(' ').map(item => parseInt(item));
    const children = [];
    for (let i = 1; i < numArr.length; i++) {
      children.push(numArr[i]);
    }
    arr.push({ node: numArr[0], children: children })
  });
  return arr;
}

// 树转数组结构
function arrToTree(arr) {
  const map = new Map();
  arr.forEach(item => {
    // 每一项添加父ID
    item.parentId = 0;
    // 设置map
    map.set(item.node, item);
  })
  arr.forEach(item => {
    for (let i = 0; i < item.children.length; i++) {
      if (map.get(item.children[i])) {
        // 用到复杂数据类型的引用
        map.get(item.children[i]).parentId = item.node;
        item.children[i] = map.get(item.children[i])
      }
    }
  })
  console.log(map);
  console.log(arr);
  // 找到根节点
  for (const item of arr) {
    if (item.parentId === 0) {
      return item;
    }
  }
}

// 层序遍历
function levelOrder(root) {
  let queue = [root];
  let res = [];
  while (queue.length) {
    let current = queue.shift();
    if (typeof current === 'number') {
      res.push(current)
    } else {
      res.push(current.node);
    }
    if (current.children && current.children.length > 0) {
      queue.push(...current.children);
    }
  }
  // 输出字符串
  return res.join(' ');
}
